// SortingAndSearching.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

void merge_(vector<int>& big, vector<int> const& small)
{
    vector<int> temp;
    auto bigIt = big.begin();
    auto smallIt = small.begin();

    while (bigIt != big.end())
    {
        while (smallIt != small.end() && *bigIt > *smallIt)
        {
            temp.push_back(*smallIt++);
        }
        temp.push_back(*bigIt++);
    }

    if (smallIt != small.end())
    {
        temp.insert(temp.end(), smallIt, small.end());
    }

    swap(big, temp);
}

void merge(vector<int>& big, vector<int> const& small)
{
    big.resize(big.size() + small.size());
    auto position = big.rbegin();
    auto bigIt = big.rbegin() + small.size();
    auto smallIt = small.rbegin();

    while (bigIt != big.rend())
    {
        while (smallIt != small.rend() && *bigIt < *smallIt)
        {
            *position++ = *smallIt++;
        }
        swap(*position++, *bigIt++);
    }

    if (smallIt != small.rend())
    {
        *position++ = *smallIt++;
    }

}

void testMerge()
{
    //11.1 You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B.
    //Write a method to merge B into A in sorted order.
    int array1[] = {0, 3, 5, 6, 7, 11,13};
    vector<int> big(array1, array1 + sizeof(array1) / sizeof(int));

    int array2[] = {1, 2, 3, 4, 5, 6, 7, 15};
    vector<int> small(array2, array2 + sizeof(array2) / sizeof(int));

    merge(big, small);

    for (int i = 0; i < big.size(); i++)
    {
        cout << big[i] << endl;
    }
}

struct AnagramsSort
{
    bool operator()(string const& a, string const& b)
    {
        auto x = a;
        auto y = b;
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        return x.compare(y) < 0;
    }
};

void testAnagrams()
{
    //11.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
    string strings[] = {"abc", "add", "edf", "cba", "dda"};
    vector<string> input(strings, strings + 5);

    map<string, vector<string>, AnagramsSort> result;

    for (int i = 0; i < input.size(); i++)
    {
        if (result.find(input[i]) != result.end())
        {
            result[input[i]].push_back(input[i]);
        }
        else
        {
            vector<string> list;
            list.push_back(input[i]);
            result[input[i]] = list;
        }
    }

    vector<string> output;
    auto it = result.begin();
    while (it != result.end())
    {
        output.insert(output.end(), (*it).second.begin(), (*it).second.end());
        ++it;
    }
}

vector<int>::iterator search(vector<int>::iterator from, vector<int>::iterator to, int x)
{
    if (*from == x)
    {
        return from;
    }
    else if(*to == x)
    {
        return to;
    }

    auto d = distance(from, to);
    auto mid = from + d / 2;

    if (*mid == x)
    {
        return mid;
    }

    if (*mid > *from)
    {
        //left side is normal
        if (x < *mid && x > *from)
        {
            return search (from, mid, x);
        }
        else 
        {
            return search (mid, to, x);
        }
    }
    else if (*mid < *to)
    {
        //right side is normal
        if (x > *mid && x < *to)
        {
            return search(mid, to, x);
        }
        else 
        {
            return search(from, mid, x);
        }
    }
    else if (*mid == *from)
    {
        return search(mid, to, x);
    }
    else if (*mid == *to)
    {
        return search(from, mid, x);
    }
    else
    {
        throw runtime_error("Run into unexpected situation.");
    }
}

void testFindElement()
{
    //11.3 Given a sorted array of n integers that has been rotated an unknown number of
    //times, write code to find an element in the array. You may assume that the array was
    //originally sorted in increasing order.
    int data[] = {7, 8, 1, 2, 3, 4, 5, 6};
    vector<int> input(data, data + sizeof(data) / sizeof(int));
    auto ret = search(input.begin(), input.begin() + 7, 8);
    cout << *ret <<endl;
}

vector<string>::iterator searchSortedString(vector<string>::iterator from, vector<string>::iterator to, string const& x)
{
    if ((*from).compare(x) == 0)
    {
        return from;
    }

    if ((*to).compare(x) == 0)
    {
        return to;
    }

    if (from == to)
    {
        return from;
    }

    auto mid = from + distance(from, to) / 2;
    if ((*mid).compare(x) == 0)
    {
        return mid;
    }

    auto left = mid;
    auto right = mid + 1;

    while (left != from && (*left).empty())
    {
        left --;
    }

    while (right != to && (*right).empty())
    {
        right ++;
    }

    if (x.compare(*left) < 0)
    {
        return searchSortedString(from, left, x);
    }
    else
    {
        return searchSortedString(right, to, x);
    }

}

void testSearchString()
{
    //11.5 Given a sorted array of strings which is interspersed with empty strings, write a
    //method to find the location of a given string.
    string strings[] = {"abc", "", "add", "", "cba", "", "dda", "", "edf"};
    vector<string> input(strings, strings + 9);
    searchSortedString(input.begin(), input.begin() + 8, "aaa");
}

void testSearchInMatrix()
{
    //11.6 Given an M x N matrix in which each row and each column is sorted in ascending
    //order, write a method to find an element.
}

void testBuildTower()
{
    //11.7 A circus is designing a tower routine consisting of people standing atop one another's
    //shoulders. For practical and aesthetic reasons, each person must be both shorter
    //and lighter than the person below him or her. Given the heights and weights of
    //each person in the circus, write a method to compute the largest possible number
    //of people in such a tower.
}

void testRankNumber()
{
    //11.8 Imagine you are reading in a stream of integers. Periodically, you wish to be able to
    //look up the rank of a number x (the number of values less than or equal to x). Implement
    //the data structures and algorithms to support these operations. That is, implement
    //the method track(int x), which is called when each number is generated,
    //and the methodgetRankOf'Number (int x), which returns the number of values
    //less than or equal to x (not including x itself).


}

int _tmain(int argc, _TCHAR* argv[])
{
    testMerge();
    testAnagrams();
    testFindElement();
    testSearchString();
    testSearchInMatrix();
    testBuildTower();
    testRankNumber();
    cin.get();
	return 0;
}

